Aspekty języków:
> Syntaktyka (składnia) - zbiór reguł określający formalnie poprawne konstrukcje językowe
> Semantyka - opisuje znaczenie konstrukcji językowych
> Pragmatyka - opisuje wszystkie inne aspekty języka
Na tych zajęciach zajmiemy się syntaktyką, czyli sposobem określania reguł poprawnych konstrukcji dla zadanych języków (w tym np. języków programowania).
Każdy język zbudowany jest na bazie alfabetu:
Alfabet \(V = \{v_0, ... , v_n\}\) -– dowolny skończony i niepusty zbiór symboli (liter), z których będą zestawiane słowa języka.
Słowo nad alfabetem \(V\) -– wszystkie skończone, uporządkowane ciągi złożone z elementów alfabetu.
Słowo puste \(\epsilon\) -– słowo nie mające żadnej litery.
Język uniwersalny \(V^{*}\) -– zbiór wszystkich słów nad alfabetem \(V\).
Język –- dowolny podzbiór języka uniwersalnego \(V^{*}\) nad \(V\).
Syntaktyka (składnia) języka -– reguły budowy zdań w języku.
Przykład:
Jeśli \(V=\{a,b\}\), to \(V^{*}=\{e, a, b, aa, ab, bb, aaa, aab,...\}\).
Gramatyką formalną nazywamy sposób opisu języka formalnego, czyli podzbioru zbioru wszystkich słów skończonej długości nad danym alfabetem.
Formalnie gramatykę określamy jako: \(G = < V, T, P, S >\)
\(V\) -– zbiór symboli terminalnych -– skończony, niepusty zbiór symboli końcowych, z których budowane są słowa generowane przez gramatykę (zwany czasem alfabetem końcowym),
\(T\) –- zbiór symboli nieterminalnych –- skończony, niepusty zbiór symboli pomocniczych,
\(P\) -– lista produkcji –- reguły gramatyki,
\(S\) -– symbol startowy (aksjomat) –- jest to wyróżniony symbol pomocniczy, z niego wyprowadzane są wszystkie generowane przez gramatyk \(G\) napisy.
Produkcją nazwiemy regułę zastępowania symbolu pomocniczego przez słowa, w skład których mogą wchodzić zarówno symbole pomocnicze, jak i końcowe. Proces wyprowadzania słów języka zdefiniowanego przez gramatykę zaczynamy od symbolu S. Do poszczególnych symboli pomocniczych stosujemy którąś z produkcji ze zbioru P tak długo, aż wszystkie symbole pomocnicze znikną.
Przykład:
Dla języka postaci \(V^{*} = \{ 1, 11, 111, ... \}\), reguły go definiujące mają postać:
Symbol początkowy: \(S\)
Słowo złożone z samych symboli końcowych, nazywamy słowem wyprowadzalnym z gramatyki. Jednym ze sposobów opisu składni języka jest np. ,,notacja BNF''.
Notacja Backusa-Naura (ang. Backus-Naur form) jest sposobem zapisu reguł gramatyki bezkontekstowej, czyli sposobem opisu języków formalnych. Notacja ta jest powszechnie używana w informatyce do zapisu składni języków programowania i protokołów komunikacyjnych. Została wymyślona przez Johna Backusa w latach 50. w czasie praca nad językiem Fortran, a następnie zmodyfikowana przez Petera Naura i użyta do zdefiniowania składni języka Algol.
Elementy notacji BNF:
Symbole nieterminalne, symbole terminalne, produkcje
\(<\ >\) - symbol pomocniczy
\(\rightarrow\) zastępowana jest przez \(::=\) - symbol czytany ,,jest równe z definicji'', łączy strony produkcji
\(|\) - symbol alternatywy
\(\{\}^n_0\) - powtórzenie 0 lub więcej razy
\([]\) - elementy opcjonalne
Przykład 1:
Aby przy pomocy notacji BNF określić liczbę naturalną, można użyć następujących reguł:
\(<\) zero \(>::= 0\)
Przykład wartości: \(0\)
\(<\) cyfra niezerowa \(>::=\ 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9\)
Przykład wartości: \(1, 2, 3\)
\(<\) cyfra \(>::=\ <\) zero \(> | <\) cyfra niezerowa \(>\)
Przykład wartości: \(0, 1, 2, 3\)
\(<\) ciąg cyfr \(> ::=\ <\) cyfra \(> | <\) cyfra \(><\) ciąg cyfr \(>\)
Przykład wartości: \(0, 1, 01, 23, 45, 99, 10023, 000001\)
\(<\) liczba naturalna \(>::=\ <\) cyfra \(> | <\) cyfra niezerowa \(><\) ciąg cyfr \(>\)
Przykład wartości: \(0, 1, 2, 34 56, 406, 556066\)
Przykład 2:
Poniżej przedstawiono prosty przykład gramatyki bezkontekstowej, zapisanej w notacji BNF, generującej liczby binarne:
\(<\) liczba_binarna \(>\ ::= <\) liczba_binarna \(> <\) cyfra \(>\)
\(<\) liczba_binarna \(>\ ::= <\) cyfra \(>\)
\(<\) cyfra \(>\ ::= 0 | 1\)
Gramatyka ta ma więc postać ogólną:
\(G= \{ V, T, P, S \}\)
\(V = \{ 0, 1 \}\)
\(T = \{ <\) liczba_binarna \(>\) , \(<\) cyfra \(>\}\)
\(P = \{<\) liczba_binarna \(>\ ::= <\) liczba_binarna \(> <\) cyfra \(>\)
\(<\) liczba_binarna \(>\ ::= <\) cyfra \(>\)
\(<\) cyfra \(>\ ::= 0 | 1 \}\)
\(S = <\) liczba_binarna \(>\)
Zadanie 1
Podaj przykład gramatyki generującej język \(\{a^nb^n : n \in \mathbb{N}\}\).
Zadanie 2
Podaj przykład gramatyki generującej język \(\{w : w \in \{a, b\}^* \wedge w=w^R\}\), który jest językiem wszystkich palindromów (wyrazów, które wyglądają tak samo niezależnie od tego, czy czytamy je normalnie, czy od tyłu) nad alfabetem \(\{a,b\}\).
Zadanie 3
Podaj przykład gramatyki generującej język \(\{a^k b^l c^n : k,l,n \in \mathbb{N}\}\), oraz takiej samej w przypadku, gdy \(k=n\).
Zadanie 4
Zdefiniować gramatykę generującą liczby binarne parzyste.
Zadanie 5
Dany jest język \(L(G)\) nad gramatyką:
\(G = <V,T,P,S>\)
\(V = \{ a, b \}\)
\(T = \{ S, A \}\)
Produkcje:
\(S \rightarrow \ aAS\ |\ a\)
\(A \rightarrow \ SbA\ |\ SS\ |\ ba\)
Czy słowo \(aabbaa\) należy do języka? Aby słowo należało do języka należy udowodnić, że a) Słowo jest wyprowadzalne z \(S\). b) Słowo to należy do \(T\).
Zadanie 6
Dana jest gramatyka:
\(G=(V,T,P,S)\)
\(V= \{ a, b \}\)
\(T = \{ A, B, S\}\)
\(P = \{ P: S \rightarrow aSB | aAS | abS | Sba | ab\)
\(A \rightarrow aa\)
\(B \rightarrow bb\}\)
\(S = C\)
Czy słowa: \(aababbabb\), \(aaaaabbb\), \(aaaabbba\) są słowami poprawnymi języka \(L(G)\) (języka wywiedzionego z tej gramatyki)?
Zadanie 7
Jaka gramatyka generuje język: \(L ={ab,bbc,ccca,aaaab,bbbbbc,cccccca...}\)
Zadanie Domowe Punktowane - 10 pkt
Dla zadanej gramatyki języka angielskiego:
<sentence> ::= <declarative> | <interrogative>
<declarative> ::= <subject> <verb> <object>
<interrogative> ::= <auxiliary verb> <subject> <predicate>
<subject> ::= <article> <noun>
<object> ::= <noun-phrase> | <article> <noun-phrase>
<predicate> ::= <verb> <object>
<noun-phrase> ::= <noun> | <adjective> <noun-phrase>
<article> ::= a | an | the
<noun> ::= boy | dad | rock | dinner
<verb> ::= throw | threw | cooks
<adjective> ::= big | yellow | tasty
<auxiliary verb> did | will
Wygeneruj 4 zdania w powyższej gramatyce.
Podaj gramatykę w której możemy wygenerować poniższe zdania:
Nr indeksu wykonał zadanie domowe.
Imię nazwisko wykonał zadanie domowe.
Nr indeksu wykonał zadanie domowe na piątkę.
Imię nazwisko wykonał zadanie domowe na czwórkę.
Nr indeksu wykonał zadanie domowe na czwórkę.
Imię nazwisko wykonał zadanie domowe na piątkę.
Nr indeksu nie wykonał zadania domowego.
Imię nazwisko nie wykonał zadania domowego.
Nr indeksu nie wykonał zadania domowego na piątkę.
Imię nazwisko nie wykonał zadania domowego na czwórkę.
Podmień jako Nr indeksu i Imię nazwisko własny numer indeksu i imię i nazwisko.
Dla gramatyki
<wyrazenia> ::= <wyrazenia> + <czynnik> | <wyrazenia> - <czynnik> | <czynnik>
<czynnik> ::= <czynnik> * <mnoznik> | <mnoznik>
<mnoznik> ::= <zmienna> | ( <wyrazenia> )
<zmienna> ::= X | Y | Z
Narysuj drzewko parsowania w powyższej gramatyce formuły:
Z - (X + Y)*X
4) Zdefiniuj gramatykę dla definicji zmiennych 4 typów prostych w języku C++ (int, char, float, bool) (dla uproszczenia nie chcemy definiować tablic, wskaźników ani referencji), inaczej mówiąc taką, byśmy mogli poprawnie wygenerować poniższe deklaracje:
int i, j, k;
float x, y;
bool found;
char a, b, c;
Wykorzystaj symbol <<nazwa>> jako oznaczenie nazwy zmiennej (nie parsujemy postaci nazwy zmiennej). Np. formuła może mieć postać
<definicje> ::= <definicje> , <<nazwa>> | <<nazwa>> ;
Uwaga! powyższa formuła niekoniecznie będzie przydatna w rozwiązaniu zadania!
Termin wykonania zadania: Sobota 7(14 lub 21).11.2015 do godziny 24.00. Proszę o przesłanie rozwiązań mailem lub dostarczenie osobiście. Odpowiedzią może być zdjęcie kartki z rozwiązaniem (byleby załącznik miał sensowny rozmiar).
Wykorzystano materiały z:
http://www.cs.put.poznan.pl/akobusinska/downloads/wprowadzenie/w7-gramatyki.pdf